1. Field of Invention
The invention preferably relates to optimized execution of object oriented languages which use the ‘interface’ abstraction, and in particular JAVA. In a preferred embodiment, the invention relates to Dispatch Mechanism for Interface Methods.
2. Description of Related Art
In recent years, there have been developments in programming languages towards what is known as an object-oriented language. In these developments, concepts are regarded as ‘objects’, each carrying with it a set of data, or attributes, pertinent to that object, as well as information relating to so-called ‘methods’, that is functions or sub-routines, that can be performed on that object and its data. This is well known to those skilled in the art of computing and/or programming.
The advent and rapid advancement in the spread and availability of computers has led to the independent development of different types of systems, such as the IBM and IBM-compatible PC running IBM-DOS or MS-DOS or MS-Windows applications, the Apple Macintosh machines running their own Apple System operating system, or various Unix machines running their own Unix operating systems. This proliferation of independent systems has led to useful applications being available only in one format and not being capable of running on a machine for which the application was not designed.
Under such circumstances, programmers have devised software which ‘emulates’ the host computer's operating system so that a ‘foreign’ application can be made to run successfully in such a way that, as far as the user is concerned, the emulation is invisible. In other words, the user can perform all of the normal functions of say a Windows-based application on a Unix machine using a Unix-based operating system without noticing that he is doing so.
A particularly notable product of this type is that developed by Insignia Solutions of High Wycombe, GB and Santa Clara, Calif., USA and known under the name ‘SoftWindows 2.0 for Powermac’. This software enables a physical Macintosh computer to emulate a PC having an Intel 80486DX processor and 80487 maths co-processor plus memory, two hard disks, IBM-style keyboard, colour display and other features normally found on recent versions of the PC-type of computer.
Furthermore, there is an ever-increasing demand by the consumer for electronics gadgetry, communications and control systems which, like computers, have developed independently of one another and have led to incompatibility between operating systems and protocols. For example, remote-control devices for video players, tape players and CD players have similar functions, analogous to ‘play,’ ‘forward,’ ‘reverse,’ ‘pause,’ etc., but the codes for transmission between the remote control, or commander, operated by the user may not be compatible either between different types of equipment made by the same manufacturer or between the same types of equipment made by different manufacturers. There would be clear benefits of having software within the equipment which can produce for example the correct ‘play’ code based upon a ‘play’ command regardless of the specific hardware used in the equipment. Such software is commonly known as a ‘Virtual Machine.’
Other uses and applications are legion: for example, set-top boxes for decoding television transmissions, remote diagnostic equipment, in-car navigation systems and so-called ‘Personal Digital Assistants.’ Mobile telephones, for instance, can have a system upgrade downloaded to them from any service provider.
Emulation software packages lend to have certain features in common, notably that they are not general purpose but are dedicated. They are of most benefit in rapid development areas and have a distinct advantage in enabling manufacturers to cut costs. In particular, they can divorce software from the physical machine, i.e., the effect of the software in the physical machine can be altered by the emulating software without having to go into the machine's native software to implement those changes.
The specific object-oriented language used in some of the implementations described later is that known as JAVA (registered trade mark to Sun Microsystems Corporation). Some of the following implementations will enable JAVA to be used in smaller devices than is currently possible because of the improved performance and/or reduced memory footprint. Future uses projected for embedded software (virtual machines) include computers worn on the body, office equipment, household appliances, and intelligent houses and cars.
While it is recognised that there are clear advantages in the use of virtual machines, especially those using object-oriented languages, there are naturally areas where it is important and/or beneficial for some of the operations that are carried out within the system to be optimised. These may include reducing the memory requirement, increasing the speed of operation, and improving the ‘transparency’ of the system when embedded in another system. One of the principal aims of the inventions described herein is to provide a Virtual Machine which is optimised to work as quickly as possible within a memory constraint of, for example, less than 10, 5, 2 or even 1 Mbyte. Such a constraint is likely to be applicable, for example, to electronics gadgetry and other equipment where cost (or size) is a major constraint.
JAVA supports single inheritance of class types, with interfaces. Interfaces themselves can be multiply inherited from other interfaces. When a concrete class claims to implement a set of interfaces, it must provide or inherit implementations of every method directly or indirectly defined by those interfaces. (See Reference [2] listed under Other Information at the end of this specification).
In object oriented programming, objects are classified in a hierarchical stricture with each object associated with attributes (data about its features or properties) and methods (functions it may perform). Typical such functions might be ‘ring’ in the context of a mobile or other telephone, or ‘play’ in the context of audio and/or video reproduction equipment. As one of the features in object-oriented languages, such as JAVA, the attributes and methods of a super class of objects are ‘inherited’ by its subclasses.
For example, as shown in FIG. 1A, “mode of transportation” 400 is the superclass of both ‘bike’ 402 and ‘car’ 404 classes of objects. The ‘car’ sub-class could be subdivided into ‘saloon’ 406 and ‘sports’ 408 and further subdivision is possible according to, for example, the make or model of sports car etc. Certain attributes of the ‘car’ sub-class, such as the number of wheels, model, and so on, will be inherited by the ‘saloon’ and ‘sports’ sub-classes. In a similar vein, methods such as ‘turn on lights’ can be common to cars within the hierarchy, but in some sub-classes the methods themselves may differ to the extent that a certain function has to be performed before lights can actually be turned on. For instance, a sports car with pop-up headlights may need to raise the lights before they can be turned on. In such a case, the inheritance has to be overridden by the need to perform a function before the function in question can be performed.
In another context, the user of a mobile or other telephone may wish to arrange for his handset to emit a different ring depending on whether the call was business or social. In this context, ‘ring’ would be termed an ‘interface.’ Its significance is that ‘ring’ is a function that a variety of objects in the hierarchy would perform (like ‘turn on lights’ in the car example above) but the actual implementation would differ from object to object. Interfaces therefore cut across hierarchies. An interface is thus a list of functions that the object can perform (such as ‘ring’ or ‘play’ or ‘record’ and so on).
Single inheritance is usually implemented using dispatch tables (otherwise known as virtual function tables). A subclass inherits the dispatch table of its superclass, extending it with any new methods, and replacing entries which have been overridden.
Multiple inheritance in languages such as C++ is normally implemented using multiple dispatch tables and offsets ((See Reference [1] listed under Other Information at the end of this specification).
The relevant data is stored in slots in a dispatch table illustrated schematically in FIG. 1B. The attributes of an object in a table 410 are always located at the same distance from the start of the object. The object includes a pointer 412 to a dispatch table of methods 414 which are always at the same distance from the start for the same function. However, when interface methods are used, as explained above, there is no longer any certainty of knowing in which slot of the dispatch table the particular function appears. This is a problem peculiar to the multiple inheritance and particularly interfaces found in JAVA language.
Up to now, the whole of the dispatch table had to be interrogated to check that the method accessed was the proper method. It had been realised that, ideally, a unique identifier would be needed for the interfaces, but in practice the table cannot be of such a size that everything within it has a unique identifier.
Reverting to the ‘play’ function analogy, there would be one dispatch table for video recorder and one for tape recorder. Each would have different interface references, so ‘play’ might be at position 2 for video recorder and position 22 for tape recorder.
The logical definition of invoking an interface method is to search the list of methods implemented directly or indirectly by the given class of object. This is clearly slow. This can be improved by searching a ‘flat’ structure which mirrors the dispatch table.
Reference [3] listed under Other Information at the end of this specification describes an optimization where the last offset at which the interface method was found is remembered, and tried as a first guess next time the invoke interface is encountered. If the guess turns out to be wrong, a fuller search is performed. This approach is based on the assumption that a given call site will tend to operate on the same type of objects.
Even if the guess is right, the destination method has to be checked to confirm that it is. In the cases where the guess is wrong, a fairly slow search is needed.
Another approach would be to use an analog of the way C++ multiple inheritance is supported.